package leetcode;


import java.util.PriorityQueue;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/19 10:08
 * 剑指 Offer 40. 最小的k个数
 */
public class Solution40 {
    public int[] getLeastNumbers(int[] arr, int k) {
        //原生的java有带你队列
        PriorityQueue<Integer> maxHeapQueue = new PriorityQueue<>((o1, o2) -> (o2-o1));

        for (int i = 0; i < k; i++) {
            maxHeapQueue.offer(arr[i]);
        }

        for (int i = k; i < arr.length ; i++) {
            if(!maxHeapQueue.isEmpty() && arr[i] < maxHeapQueue.peek()){
                maxHeapQueue.poll();
                maxHeapQueue.offer(arr[i]);
            }
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = maxHeapQueue.remove();
        }
        return res;
    }


    public static void main(String[] args) {
        int[] arr = {3,2,1};
        int k = 2;

        int[] leastNumbers = new Solution40().getLeastNumbers(arr, k);
        for (int i = 0; i < leastNumbers.length; i++) {
            System.out.println(leastNumbers[i]);
        };
    }
}
